; TODO 
;  - fold
;  - fix bug in old galore code (see test example)

(module dequeue mzscheme
  (provide 
   deque-empty?
   deque-insert
   deque-insert-last
   deque-insert-first
   deque-remove
   deque-remove-first
   deque-remove-last
   deque-first
   deque-elements
   ;deque-fold
   deque-last)
  
  (require (lib "etc.ss")
           (prefix list: (lib "list.ss"))
           (lib "unitsig.ss")
           "../queue.ss")


  ; A general set consists of a "vector" of methods, a size and a specialized
  ; representation of the set.

  (define-struct <deque> 
    (methods   ;  methods
     deque       ; the specialized representation
     ))

  (define (deque? o) (<deque>? o))

  
  (define-struct deque-methods 
    ; IMPORTANT: When adding more methods, remember to add a keyword in 'call' below
    (empty? insert-last insert-first remove-first remove-last
            first elements fold last))

  ; (call method-name methods . arguments) 
  ;   sugar coats the method calls
  (define-syntax call
    (syntax-rules (empty? insert-last insert-first remove-first remove-last
                             first last elements fold)
      ((call m empty?       s)     ((deque-methods-empty?                 m) s))
      ((call m insert-last  s x)   ((deque-methods-insert-last            m) s x))
      ((call m insert-first s x)   ((deque-methods-insert-first           m) s x))
      ((call m insert-all   s xs)  ((deque-methods-insert-all             m) s xs))
      ((call m remove-first s)     ((deque-methods-remove-first           m) s))
      ((call m remove-last  s)     ((deque-methods-remove-last            m) s))
      ((call m first        s)     ((deque-methods-first                  m) s))
      ((call m last         s)     ((deque-methods-last                   m) s))
      ((call m elements     s)     ((deque-methods-elements               m) s))
      ((call m fold         s f i) ((deque-methods-fold                   m) s f i))
      ((_ . more)                
       (error "call: unknown <deque> method: " '(call . more)))))
   
  (define make-deque
    (opt-lambda ([deque@ batched-deque@])
      (use-deque deque@)
      (make-<deque> (make-deque-methods empty? insert-last insert-first remove-first remove-last
                                        first last elements fold)
                    empty)))
  
  (define-syntax with-deque 
    (syntax-rules ()
      [(with-deque () body)              body]
      [(with-deque ((s m d)) body)       (let ((m (<deque>-methods s))
                                               (d (<deque>-deque s)))
                                           body)]
      [(with-deque ((s m d) . more) body)  (with-set ((s m d))
                                                     (with-deque more
                                                                 body))]))
  
  (define (deque-empty? q)            (with-deque ((q m d)) (call m empty? d)))
  (define (deque-insert-last q x)     (with-deque ((q m d)) (make-<deque> m (call m insert-last d x))))
  (define (deque-insert-first q x)    (with-deque ((q m d)) (make-<deque> m (call m insert-first d x))))
  (define (deque-remove-last q)       (with-deque ((q m d)) (make-<deque> m (call m remove-last d))))
  (define (deque-remove-first q)      (with-deque ((q m d)) (make-<deque> m (call m remove-first d))))
  (define (deque-first q)             (with-deque ((q m d)) (call m first d)))
  (define (deque-elements q)          (with-deque ((q m d)) (call m elements d)))
;  (define (deque-fold fn init q)      (with-deque ((q m d)) (call m empty? d)))
  (define (deque-last q)              (with-deque ((q m d)) (call m last d)))

  (define (deque-insert q x)  (deque-insert-last q x))
  (define (deque-xinsert q x) (deque-insert-last x q))
  (define (deque-remove q)    (deque-remove-first q))

  (define (test)
    (printf 
     "~a~n"
     (deque-elements (deque-remove (deque-remove (list:foldl deque-xinsert (make-deque) '(1 2 3 4)))))))
  (test))
